package lhc.alg.top100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * description: https://leetcode.cn/problems/3sum/
 *  三数之和  排序+左右指针
 * author: hongchen.liao
 * date:  2022/9/18
 */
public class _15_ {

    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();
            int n = nums.length;
            Arrays.sort(nums);
            for(int i = 0; i < n; i++){
                if(i > 0 && nums[i-1] == nums[i]) continue;
                int left = i+1;
                int right = n-1;
                while(left < right){
                    int sum = nums[i] + nums[left] + nums[right];
                    if(sum == 0){
                        List<Integer> sub = new ArrayList<>();
                        sub.add(nums[i]);
                        sub.add(nums[left]);
                        sub.add(nums[right]);
                        list.add(sub);
                        while(left < right && nums[left] == nums[left+1]) left++;
                        while(left < right && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }else if(sum < 0){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
            return list;
        }
    }


}
